from typing import *


class Solution:
    def lengthAfterTransformations(self, s: str, t: int, nums: List[int]) -> int:
        base = [[0] * 26]

        for v in s:
            base[0][ord(v) - ord("a")] += 1
        mul = [[0] * 26 for _ in range(26)]
        for i, v in enumerate(nums):
            for j in range(v):
                mul[i][(i + 1 + j) % 26] = 1
        mod = 1000000007

        def multiply(a, b):
            m, n, p = len(a), len(a[0]), len(b[0])
            ans = [[0] * p for _ in range(m)]
            for i in range(m):
                for j in range(p):
                    for k in range(n):
                        ans[i][j] += a[i][k] * b[k][j]
                        ans[i][j] %= mod
            return ans

        def power(p, q):
            n = len(p)
            ans = [[0] * n for _ in range(n)]
            for i in range(n):
                ans[i][i] = 1
            while q > 0:
                if q & 1 == 1:
                    ans = multiply(ans, p)
                p = multiply(p, p)
                q >>= 1

            return ans

        ret = multiply(base, power(mul, t))
        return sum(sum(r) % mod for r in ret)


so = Solution()
ans = so.lengthAfterTransformations(
    "add",
    1024,
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2],
)
print(ans, ans == 641042568)
